package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class t18 {
    public static void main(String[] args) {
        new Solution18().fourSum(new int[]{1000000000,1000000000,1000000000,1000000000},-294967296);
    }
}
class Solution18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>>ret=new ArrayList<>();
        Arrays.sort(nums);
        for (int i=0;i<nums.length;i++){
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            for (int j=i+1;j< nums.length;j++){
                int sum=nums[i]+nums[j];
                if (sum>0&&sum>target){
                    break;
                }
                if (j>i+1&&nums[j]==nums[j-1])continue;
                int left=j+1;
                int right= nums.length-1;
                while (left<right){
                    if (target==nums[left]+nums[right]+sum){
                        List<Integer>minRet=new ArrayList<>();
                        minRet.addAll(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        ret.add(minRet);
                        while (left< nums.length-1&&nums[left]==nums[left+1]){
                            left++;
                        }
                        while (right>0&&nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }else if (target<nums[left]+nums[right]+sum){
                        right--;
                    }else if (target>nums[left]+nums[right]+sum){
                        left++;
                    }

                }
            }
        }
        return ret;
    }
}